package com.guqj.basis.datastruct;

/**
 * 用array[n]数组实现的至多含有n-1个元素的队列的方法. 队列具有属性head[Q],指向队列的头. 属性tail[Q]指向新元素要被插入的地方
 * 
 * @see http://blog.csdn.net/javazejian/article/details/53375004
 * @author guqj
 * @date 2017年3月22日
 * @param <T>
 */
public class Queue<T> {

	private T[] items;
	private final static int DEFAULT_CAPACITY = 0x10;
	private int head = 0;
	private int tail = 0;

	public Queue() {
		this(DEFAULT_CAPACITY);
	}

	@SuppressWarnings("unchecked")
	public Queue(int capacity) {
		this.items = (T[]) new Object[capacity];
	}

	// 入队
	public void enqueue(T e) {
		// 判断队列是否已满
		if (this.head == (this.tail + 1) % this.items.length) {
			ensureCapacity(items.length * 2 + 1);
		}
		items[tail] = e;
		this.tail = (this.tail + 1) % items.length;
	}

	// 返回队头
	public T peek() {
		return this.items[this.head];
	}

	// 出队
	public T dequeue() {
		T temp = this.items[this.head];
		this.head = (this.head + 1) % this.items.length;
		return temp;
	}

	/**
	 * 扩容的方法
	 * 
	 * @param capacity
	 */
	@SuppressWarnings("unchecked")
	public void ensureCapacity(int capacity) {
		T[] old = items;
		items = (T[]) new Object[capacity];
		int j = 0;
		// 复制元素
		for (int i = this.head; i != this.tail; i = (i + 1) % old.length) {
			items[j++] = old[i];
		}
		// 恢复front,rear指向
		this.head = 0;
		this.tail = j;
	}

	public static void main(String[] args) {
		Queue<String> s = new Queue<>(3);
		for (int i = 0; i < 5; i++) {
			if(i == 2){
				System.out.println(s.dequeue());
			}
			s.enqueue("a " + i);
		}
		System.out.println(s.dequeue());
	}
}
